#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
	memset(buffer, 0, PageFile::PAGE_SIZE);		// clear buffer
	rc = pf.read(pid, buffer);					// read page from PageFile
	return rc; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc;
	rc = pf.write(pid, buffer);			// write buffer to the page
	return rc; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int count = 0;
	int size = sizeof(int) + sizeof(RecordId);
	for (int i = sizeof(RecordId); i < PageFile::PAGE_SIZE - sizeof(PageId); i += size)
	{
		if ( *((int*) &buffer[i]) > 0 )
			count++;
		else
			break;
	}
	return count;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int num_keys = getKeyCount();
	int size = sizeof(int) + sizeof(RecordId);
	if (num_keys < PageFile::PAGE_SIZE/size)		// if node is not full
	{
		int i;
		for (i = sizeof(RecordId); i < num_keys * size; i += size)		// iterate through the keys
		{
			if ( *((int*) &buffer[i]) > key )		// if current key is bigger than key being inserted
			{
				// insert new key and rid before this pair and shift the rest down
				int key_to_insert = key;
				RecordId rid_to_insert = rid;
				while ( *((int*) &buffer[i]) > 0 )
				{
					int temp_key;
					RecordId temp_rid;
					
					// save current key and rid
					memcpy(&temp_key, &buffer[i], sizeof(int));
					memcpy(&temp_rid, &buffer[i-sizeof(RecordId)], sizeof(RecordId));
					
					// replace with key and rid we wanted inserted
					memcpy(&buffer[i], &key_to_insert, sizeof(int));
					memcpy(&buffer[i-sizeof(RecordId)], &rid_to_insert, sizeof(RecordId));
					
					// insert the saved key and rid next
					key_to_insert = temp_key;
					rid_to_insert = temp_rid;
					
					i += size;
				}
				
				// insert last (key, rid) pair
				memcpy(&buffer[i], &key_to_insert, sizeof(int));
				memcpy(&buffer[i-sizeof(RecordId)], &rid_to_insert, sizeof(RecordId));
				return 0;
			}
		}
		
		// if key is bigger than current keys in node, insert after all keys
		memcpy(&buffer[i], &key, sizeof(int));
		memcpy(&buffer[i-sizeof(RecordId)], &rid, sizeof(RecordId));
		return 0;
	}
	else
		return RC_NODE_FULL; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	// return error if sibling is not empty
	if (sibling.getKeyCount() > 0)
		return RC_INVALID_ATTRIBUTE;		
		
	int entry_size = sizeof(int) + sizeof(RecordId); 
	int num_keys = getKeyCount() + 1; 			// number of keys after insertion
	siblingKey = *((int*) &buffer[num_keys / 2 * entry_size+sizeof(RecordId)]);

	// insert second half of keys into sibling
	int i;
	int midPos= -1;	
	for (i = 0 ; i <= (num_keys-2) * entry_size ; i += entry_size ) 
	{
		if (*((int*) &buffer[i+sizeof(RecordId)]) >= siblingKey)
		{
			if (midPos == -1)
				midPos = i;
			RecordId temp_rid;
			memcpy(&temp_rid, &buffer[i], sizeof(RecordId));
			sibling.insert(*((int*) &buffer[i+sizeof(RecordId)]), temp_rid);
		}
	}

	// clear second half of node
	memset(&buffer[midPos], 0, PageFile::PAGE_SIZE - midPos - sizeof(PageId));

	// insert new (key, rid) pair into appropriate node
	if ( key < siblingKey )
		insert(key, rid); 
	else
		sibling.insert(key, rid);
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	int num_keys = getKeyCount();
	int size = sizeof(int) + sizeof(RecordId);
	for (int i = sizeof(RecordId); i < num_keys * size; i += size)		// iterate through keys
	{
		// if key >= searchKey, return eid
		if (*((int*) &buffer[i]) >= searchKey)		
		{
			eid = i/size;
			return 0;
		}
	}
	
	return RC_NO_SUCH_RECORD; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int size = sizeof(int) + sizeof(RecordId);
	
	// return error if eid is negative or too large
	if (eid < 0 || eid > PageFile::PAGE_SIZE / size)		
		return RC_NO_SUCH_RECORD;
		
	//key = *((int*) &buffer[eid*size + sizeof(RecordId)]);
	key = (int) &buffer[eid*size + sizeof(RecordId)];
	memcpy(&rid, &buffer[eid*size], sizeof(RecordId));
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	return *((PageId*) &buffer[PageFile::PAGE_SIZE - sizeof(PageId)]); 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	memcpy(&buffer[PageFile::PAGE_SIZE - sizeof(PageId)], &pid, sizeof(PageId));
	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	RC rc;
	memset(buffer, 0, PageFile::PAGE_SIZE);		// clear buffer
	rc = pf.read(pid, buffer);					// read page from PageFile
	return rc; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	RC rc;
	rc = pf.write(pid, buffer);			// write buffer to the page
	return rc; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int count = 0;
	int size = sizeof(int) + sizeof(PageId);
	for (int i = sizeof(PageId); i <= PageFile::PAGE_SIZE - size; i += size)
	{
		if ( *((int*) &buffer[i]) > 0 )
			count++;
	}
	
	return count;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int num_keys = getKeyCount();
	int size = sizeof(int) + sizeof(PageId);
	if (num_keys < (PageFile::PAGE_SIZE-sizeof(PageId))/size)		// if node is not full
	{
		int i;
		for (i = sizeof(PageId); i <= num_keys * size; i += size)		// iterate through the keys
		{
			if ( *((int*) &buffer[i]) > key )		// if current key is bigger than key being inserted
			{
				// insert new key and pid before this pair and shift the rest down
				int key_to_insert = key;
				PageId pid_to_insert = pid;
				while ( *((int*) &buffer[i]) > 0 )
				{
					int temp_key;
					PageId temp_pid;
					
					// save current key and pid
					memcpy(&temp_key, &buffer[i], sizeof(int));
					memcpy(&temp_pid, &buffer[i+sizeof(int)], sizeof(PageId));
					
					// replace with key and pid we wanted inserted
					memcpy(&buffer[i], &key_to_insert, sizeof(int));
					memcpy(&buffer[i+sizeof(int)], &pid_to_insert, sizeof(PageId));
					
					// insert the saved key and pid next
					key_to_insert = temp_key;
					pid_to_insert = temp_pid;
					
					i += size;
				}
				
				// insert last (key, pid) pair
				memcpy(&buffer[i], &key_to_insert, sizeof(int));
				memcpy(&buffer[i+sizeof(int)], &pid_to_insert, sizeof(PageId));
				return 0;
			}
		}
		
		// if key is bigger than current keys in node, insert after all keys
		memcpy(&buffer[i], &key, sizeof(int));
		memcpy(&buffer[i+sizeof(int)], &pid, sizeof(PageId));
		return 0;
	}
	else
		return RC_NODE_FULL; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	if (sibling.getKeyCount() > 0)
		return RC_INVALID_ATTRIBUTE;		// return error if sibling is not empty
		
	int num_keys = getKeyCount();		 					
	int size = sizeof(int) + sizeof(PageId);
	midKey = *((int*) &buffer[num_keys / 2 * size + sizeof(PageId)]);
	
	// insert second half of keys into sibling
	int i;
	int midPos = -1;
	for (i = sizeof(PageId); i <= (num_keys-1) * size; i += size)
	{
		if ( *((int*) &buffer[i]) >= midKey )
		{
			if ( midPos == -1 )
				midPos = i;
			PageId temp_pid;
			memcpy(&temp_pid, &buffer[i+sizeof(int)], sizeof(int));
			sibling.insert(*((int*) &buffer[i]), temp_pid);
		}
	}

	// clear second half of node, including midKey
	memset(&buffer[midPos], 0, PageFile::PAGE_SIZE - midPos);
	
	// insert new (key, rid) pair into appropriate node
	if (key < midKey)
		insert(key, pid);
	else
		sibling.insert(key, pid);
	
	return 0;

}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int size = sizeof(int) + sizeof(PageId);
	int i;
	
	memcpy(&pid, &buffer[0], sizeof(PageId));		
	
	// iterate through keys
	for (i = sizeof(PageId); i <= PageFile::PAGE_SIZE-size; i += size)		
	{
		// if searchKey >= key, return pid right before it
		if (searchKey >= *((int*) &buffer[i]) && *((int*) &buffer[i]) > 0)		
		{
			memcpy(&pid, &buffer[i+sizeof(int)], sizeof(PageId));
		}
	}
	
	return 0;

}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	memset(buffer, 0, PageFile::PAGE_SIZE);		// clear buffer
	memcpy(&buffer[0], &pid1, sizeof(PageId));
	memcpy(&buffer[sizeof(PageId)], &key, sizeof(int));
	memcpy(&buffer[sizeof(PageId) + sizeof(int)], &pid2, sizeof(PageId));
	return 0;
}
